//你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。 
//
// 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表
//示如果要学习课程 ai 则 必须 先学习课程 bi 。 
//
// 
// 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 
// 
//
// 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//输入：numCourses = 2, prerequisites = [[1,0]]
//输出：true
//解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。 
//
// 示例 2： 
//
// 
//输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
//输出：false
//解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。 
//
// 
//
// 提示： 
//
// 
// 1 <= numCourses <= 2000 
// 0 <= prerequisites.length <= 5000 
// prerequisites[i].length == 2 
// 0 <= ai, bi < numCourses 
// prerequisites[i] 中的所有课程对 互不相同 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 👍 1670 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author ldltd
 * @date 2023-08-25 00:54:35
 * @description 207.课程表
 */
public class CourseSchedule{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new CourseSchedule().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*方法一： 从入度思考(从前往后排序)，
		 入度为0的节点在拓扑排序中一定排在前面,
		 然后删除和该节点对应的边, 迭代寻找入度为0的节点。

		 方法二： 从出度思考(从后往前排序)，
		 出度为0的节点在拓扑排序中一定排在后面,
		 然后删除和该节点对应的边, 迭代寻找出度为0的节点。*/
		 /*dfs  判断是否有环
		 * 时间空间om+n*/
	//保存边
	List<List<Integer>> edges;
	//是否访问
	int []visited;
	//结果
	boolean valid=true;
	//dfs，判断是否有环
    public boolean canFinish(int numCourses, int[][] prerequisites) {
		edges=new ArrayList<List<Integer>>();
		//至少有numCourses个list
		for (int i = 0; i < numCourses; i++) {
			edges.add(new ArrayList<Integer>());
		}
		// prerequisites = [[1,0]]  学习课程 1 之前，你需要完成课程 0
		//把0的后置课程放进去
		for (int[] prerequisite : prerequisites) {
			edges.get(prerequisite[1]).add(prerequisite[0]);
		}
		visited=new int[numCourses];
		for (int i = 0; i < numCourses && valid; i++) {
			if(visited[i]==0){
				dfs(i);
			}
		}
		return valid;
    }

	private void dfs(int u){
		//搜索中
		visited[u]=1;
		//对u的任意前节点v，
		//如果未搜索，则继续搜索，
		//如果搜索中，说明存在环
		//如果搜索完，就返回
		for (int v : edges.get(u)) {
			if(visited[v]==0){
				dfs(v);
				if(!valid){
					return;
				}
			}else if(visited[v]==1){
				valid=false;
				return;
			}
		}
		//搜索完
		visited[u]=2;
	}
	/*bfs  时间空间omn*/
	public boolean canFinish1(int numCourses, int[][] prerequisites) {
		Queue<Integer>q=new LinkedList<>();
		edges=new ArrayList<List<Integer>>();
		for (int i = 0; i < numCourses; i++) {
			edges.add(new ArrayList<Integer>());
		}
		//这里visited的定义是，某个点的入度
		visited=new int[numCourses];
		for (int[] prerequisite : prerequisites) {
			edges.get(prerequisite[1]).add(prerequisite[0]);
			visited[prerequisite[0]]++;
		}

		/*   出度写法
		*   //记录每个课程的出度
            for(int [] p:prerequisites){
                edge.get(p[0]).add(p[1]);
                vis[p[1]]++;
            }
		* */
		for (int i = 0; i < numCourses; i++) {
			//把入度为0的点加入
			if(visited[i]==0){
				q.offer(i);
			}
		}
		//记录访问数
		int vis=0;
		while (!q.isEmpty()){
			++vis;
			int u = q.poll();
			for (int v : edges.get(u)) {
				//v的入度-1，减的就是u
				--visited[v];
				//如果v没有前置课程了，则加入队列中
				if(visited[v]==0){
					q.offer(v);
				}
			}
		}
		return vis==numCourses;
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
